package goleetcode

import "duan.com/leetcode/utils"

func allPossibleFBT(n int) []*utils.TreeNode {
	var fullBsts []*utils.TreeNode
	if n % 2 == 0 {
		return fullBsts
	}
	if n == 1 {
		fullBsts = append(fullBsts, &utils.TreeNode{Val: 0})
		return fullBsts
	}
	for i := 1; i < n; i += 2 {
		leftSubTrees := allPossibleFBT(i)
		rightSubTrees := allPossibleFBT(n - 1 - i)
		for _, leftSubTree := range leftSubTrees {
			for _, rightSubTree := range rightSubTrees {
				root := &utils.TreeNode{Val: 0, Left: leftSubTree, Right: rightSubTree}
				fullBsts = append(fullBsts, root)
			}
		}
	}
	return fullBsts
}
